package ThirdWeek;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Tuesday {
    //30、串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new LinkedList<>();

        Map<String,Integer> hash1 = new HashMap<>();
        for (String word : words) {
            hash1.put(word,hash1.getOrDefault(word,0) + 1);
        }
        //我们要比较len这个长度的次数，并且把每一个字符串当成一个字符，每次right走right+len这个长度的步数
        int len = words[0].length(),n = s.length(),m = words.length;
        for (int i = 0; i < len;i++) {
            Map<String,Integer> hash2 = new HashMap<>();
            for(int left = i,right = i,count = 0;right + len <= n;right += len) {
                //进窗口
                String in = s.substring(right,right + len);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0)) {
                    count++;
                }
                if (right - left + 1 > m * len) {
                    String out = s.substring(left,left + len);
                    hash2.put(out,hash2.get(out) - 1);
                    left += len;
                    if (hash2.get(out) < hash1.getOrDefault(out,0)) {
                        count--;
                    }
                }
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    //438、找到字符串中所有字母的异位词
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new LinkedList<>();

        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int m = pp.length;
        int n = ss.length;
        int[] hash1 = new int[26];
        for (char ch : pp) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        for(int left = 0,right = 0,count = 0; right < n;right++) {
            //count 是有效数据的个数
            char ch = ss[right];
            if(++hash2[ch - 'a'] <= hash1[ch - 'a']) {
                //判断是否存入的是有效数据
                count++;
            }
            //窗口的长度是固定的，所以我们只需要判断一下就可以了，当窗口长度一定的时候
            if ((right - left + 1) > m) {
                //超过窗口的长度
                //进行出窗口 判断出去的字符是否是有效字符，如果是count--
                char out = ss[left++];
                if (--hash2[out - 'a'] < hash1[out - 'a']) {
                    count--;
                }
            }
            //当有效字符的长度和p这个字符串的长度相等的时候，就是需要把 left 这个下标入 链表中
            if (count == m) {
                list.add(left);
            }
        }
        return list;
    }

    //58、最后一个单词的长度
    public int lengthOfLastWord(String s) {
        //反向遍历
        int last = s.length() - 1;
        while(s.charAt(last) == ' ') {
            //去除字符串的会后面出现空格的次数
            last--;
        }
        int lastWordLength = 0;
        while(last >= 0 && s.charAt(last) != ' ') {
            lastWordLength++;
            last--;
        }
        return lastWordLength;
    }

    //35、搜索插入位置
    public int searchInsert1(int[] nums, int target) {
        // 二分查找
        //这里我们使用 在数组中查找target的位置，但出现多个target的时候就是查找左端点
        int left = 0,right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        //这个target比所有的数据都大的时候就是在数组长度的位置插入
        if (nums[right] < target) {
            return right + 1;
        }
        return right;
    }

    public int searchInsert(int[] nums, int target) {
        // 二分查找
        //这里使用的是朴素二分查找
        int n = nums.length;
        //如果这个要插入的值是比数组都大的值的话就是插入数组长度的位置，所以设置ret为数组长度
        int left = 0,right = n - 1,ret = n;
        while (left <= right) {
            //int mid = (right - left) >>(相当于是“/”) 1 + left;
            int mid = (right + left) / 2;
            if (target <= nums[mid]) {
                ret = mid;
                right = mid - 1;
            }else {
                //为什么满足这个条件target <= nums[mid]，可以更改返回值？
                //因为 当满足这个条件的时候呢，我们的 target 就一定会死插入到mid和left中间了，
                //不满足这个条件的话，我们的target比mid这个位置的值大，就不会插入到比其小的位置
                left = mid + 1;
            }
        }
        return ret;
    }
}
